간단한 실험을 했다. 간단한 실험이라 실제 어떤 식으로 오차가 전개될지는 모른다.
궁금한 점은 이렇다. 테이블 n칸이 있다. 각 칸에는 검색키가 들어있고, 대형 파일을 검색할 예정이다. 별다른 알고리즘을 쓰지 않는다고 가정하면 파일을 1바이트씩 전진하며 테이블 n을 루핑하며 키를 검색한다. 아호코라식이니 KMP등등은 일단 제껴놓자.
이때 테이블 n칸을 루핑하는 비용이 크다고 할 수 있다.
이제 이것을 n개의 쓰레드로 나누자. 그런데 CPU는 코어가 4개다. 하이퍼쓰레드로는 8개다. 일단 4개로 나눠서 작업하면 빨라질 것이다. 테이블 스캔 비용이 n에서 n/4가 된다. 쓰레드 전환 비용이 있긴 하지만 아직까지는 물리 코어를 다 쓸 수 있다.
이제 쓰레드를 8개로 나누자. 이제 하이퍼쓰레드로서 8코어를 쓴다. 어쨌든 인텔도 머리써서 만든 아키텍쳐이므로 빨라진다. 테이블 스캔 비용은 n/8이 되었다.
이제 쓰레드를 16개로 나누자. 8 쓰레드에서 물리코어를 완전히 다 썼으므로 쓰레드 끼리도 본격 코어 경쟁에 들어간다. 쓰레드 스위칭 비용이 테이블 스캔 비용을 넘어설 것인가? 이제 고민을 해야 할 때다.
실험 결과는 이렇다. 4코어 (하이퍼 8코어) 머신이다.
8쓰레드에서 16쓰레드로 넘어오면서 물리 코어에 대한 쓰레드간 점유 경쟁이 일어나고 스위칭 비용 증가가 테이블 스캔 비용 감소분 보다 크지 않을까 했는데 소폭이긴 하지만 일단 빨라지긴 했다. IO 비용이 큰 놈들이야 쓰레드가 많아도 괜찮다. CPU가 놀 수 있는 구멍이 사방에 있다. 아파치 띄우면서 백쓰레드 천쓰레드 띄워도 괜찮다. 그래야 예쁘다. 그런데 이 실험(SSD 상에서) 처럼 IO 비용이 작은 애들은 컴퓨터를 거의 풀로 쓴다. 이렇게 빡빡하게 쓰는 와중에 쓰레드 스위칭이 일어나도 테이블 스캔 많이 하는 것 보다 비용이 작을 수 있다는 것이다. 게다가 이 실험은 테이블의 키가 겨우 16개 짜리다. 큰 테이블이라면 격차는 더 커질 수도 있것따. 테이블 루핑 스캔이라는 것이 좀 그렇다. 무식한 루프다. 요즘 컴파일러 좋고 씨퓨들 예측 분기 잘한다고 해도 그게 들어맞는 케이스에서 그런거지 파이프 다 깨먹고 뭐 그런것 같다. 루프만 풀어줘도 시간이 단축되는 걸 보면 대충 맞는 추정인 것 같다. 매번 하는 말인데 용처가 한정적이라면 트리 등을 이용한 것보다는 벡터를 선호한다. O(n)이 확 늘어나도 캐시와 빠이프의 화력이 있으니.. 결정적으로 코드가 쉬워요 핳핳하하...
문제는 있다. 기계를 풀로 땡겨쓰니 이 일 말고는 다른 일을 할 수가 없다... 사천만 땡겨줘요..~
뭐.. 그렇다는 거시다.. 리눅스 한정. 끗..